package cn.com.algorithm.lru;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * 使用jdk连表实现LRU
 */
public class LRUCache2 {
    //Define map mapping
    private Map<String, Node> map;
    //Define cache capacity
    private int capacity = 8;

    private LinkedList<Node> list = new LinkedList<>();

    //Read data from cache
    public int get(String key) {
        Node node = map.get(key);
        //If it can be found, move the node to the head of the linked list without returning - 1
        if (node != null) {
            list.remove(node);
            list.addFirst(node);
            return node.value;
        }
        return -1;
    }

    // Add node to cache
    public void put(String key, int value) {
        if(capacity == 0)   return;
        Node node = map.get(key);
        if (node != null) {
            //If it exists, modify the value of this point and move it to the head of the linked list
            node.value = value;
            list.remove(node);
            list.addFirst(node);
            return;
        }

        //If it does not exist, first judge whether the cache space is sufficient
        if (list.size() == capacity) {
            //If it exists, delete the in the map and LinkedList
            map.remove(list.getLast().key);
            list.removeLast();
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        list.addFirst(newNode);
    }


    public LRUCache2(int capacity) {
        this.capacity = capacity;
        //It also defines the capacity of the map. In fact, this step is not necessary
        map = new HashMap<>(capacity);
    }


    public LRUCache2() {
        map = new HashMap<>(this.capacity);
    }

    public static class Node {
        public String key;
        public int value;

        public Node(String key, int value) {
            this.key = key;
            this.value = value;
        }

        public Node() {
        }
    }

    public static void main(String[] args) {
        LRUCache2 cache = new LRUCache2(2);
        cache.put("key1",1);
        cache.put("key2",2);
        System.out.println(cache.get("key2"));  //21
        cache.put("key3",3);
        System.out.println(cache.get("key1"));  //32
    }

}